1. מערך של מספרים וצריך להחזיר את מספר התתי מערכים שהם או סדרה עולה או סדרה יורדת או סדרה קבועה, לדוגמא המערך [1,2,4,7,6,6,6,2,0]
יש לו 4 תת יורדים ואלה האינדקסים (3,4) (6,7) (6,8) (7,8)
6 עולים (0,1),(0,2),(0,3),(1,2),(1,3),(2,3)
ו3 קבועים (4,5) (4,6) (5,6)
2. https://stackoverflow.com/questions/54449061/average-test-score-from-result-array-with-varying-group-sizes
זאת השאלה השנייה
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2020
int solution(int A[],int N){
int counters[N] = {0};
for(int i=0; i
if(A[i]>=1 && A[i]<=N)
counters[A[i-1]]++;
for(int j=1;j<=N;j++)
if(counters[j-1]==0)
return j;
return N+1;
}
דצמבר 2022
השאלה היא האם יש מספרים שליליים. אם כן אנחנו יכולים לוותר על זיכרון נוסף של counters. נניח שאין מספרים שליליים או שלפחות 'נמחק' אותם (אנחנו עוברים פעם ראשונה ומוחקים כל מספר שלילי ואפסים ושמים במקומם 1 - כי מספר שלילי והמספר אפס בכל מקרה לא מעניינים אותנו ולא משנים את התוצאה). אם לא נראה את המספר 1 (מבלי שהפכנו מספר שלילי ל1) אז ישר נחזיר שהמספר 1 חסר.
ואז נעבור על המערך פעם שנית - על כל מספר x בין 1 לבין N (- גודל המערך) שנקבל - נלך לתא הx-1 ונשנה את ערכו מחיובי לשלילי, (ככה נסמן שכבר ראינו את המספר שמסמל את התא הזה).
כל מספר אחר (x הוא 0 או גדול מN) נדלג עליו ולא נעשה כלום.
ככה נמשיך עד שנגיע לסוף המערך.
נעבור על המערך פעם שלישית. הפעם נבדוק כל ערך בתא i - אם הוא שלילי - נמשיך הלאה (זה אומר שאכן ביקרנו את התא i ושינינו את ערכו לשלילי).
אם הוא לא שלילי, נחזיר את האינדקס (i) פלוס 1 - כי בעצם לא ביקרנו בו ולא שינינו אותו לשלילי.
סה"כ הזיכרון שהשתמשנו הוא O(1) - בשביל boolean לבדוק האם ראינו כבר את המספר 1 או לא, במעבר הראשון.
ראיון לתפקיד 
